0% completed
Big-Theta Notation (Θ-notation) provides a way to describe the exact bound on the growth rate of an algorithm. It gives both an upper and a lower bound, indicating that the algorithm's performance is tightly bounded within a specific range.
- Purpose: It shows that a function
grows at the same rate as another function for large input sizes. - Usefulness: While Big-O tells us the upper bound, Θ-notation provides a more accurate description by showing the algorithm's behavior in both the worst and best cases.
Formal Definition of Big-Theta Notation
A function
for all
and are constants that scale the function . is a threshold value where the inequality holds for all larger values of .
Understanding Big-Theta Through an Example
Let’s see how to find the
Example:
-
Identify the Dominant Term:
The dominant term here is
, as it grows faster than and when becomes large. -
Choose
as the Dominant Term: Let’s set
. Now we need to find constants , , and such that:
-
Finding Suitable Constants:
- For the lower bound, we can choose
and find an where the inequality holds. - For the upper bound, we can choose
for large enough .
- For the lower bound, we can choose
-
Conclusion:
Since we have found values of
, , and , we can conclude:
How Does Θ-notation Compare with Big-O?
- Big-O Notation: Describes only the upper bound, focusing on the worst-case scenario.
- Θ-Notation: Provides both upper and lower bounds, giving a tighter description of an algorithm’s performance.
Key Properties of Big-Theta
- Exact Bound: Θ-notation tightly bounds the algorithm within a specific range.
- Symmetric Bound: It indicates that
grows at the same rate as for sufficiently large . - Best and Worst Case Covered: While Big-O may overestimate performance, Θ provides a precise characterization.
On this page
Formal Definition of Big-Theta Notation
Understanding Big-Theta Through an Example
Example:
How Does Θ-notation Compare with Big-O?
Key Properties of Big-Theta